import java.util.Arrays;
import java.util.Random;

public class SmallestK {
    public static void main(String[] args) {
        SmallestK smallestK = new SmallestK();
        int[] arr = {19,20,87,44,8,9,7,4,3,2,1,0};
        int k = 1;
        int[] ret = smallestK.smallestK(arr,k);
        System.out.println(Arrays.toString(ret));

        System.out.println(Arrays.toString(arr));
    }
    public int[] smallestK(int[] arr, int k) {
        quickSelect(arr, 0, arr.length - 1, k);
        int[] nums = new int[k];
        for(int i = 0; i < k; i++) {
            nums[i] = arr[i];
        }
        return nums;
    }

    public void quickSelect(int[] arr, int l, int r, int k) {
        if(l >= r) {
            return;
        }
        // 1.随机选择基准元素
        // int pivotIndex = ;
        int pivot = arr[new Random().nextInt(r - l + 1) + l];

        // 2.定义三个指针划分区域
        int left = l - 1, i = l, right = r + 1;
        while(i < right) {
            if(arr[i] < pivot) {
                swap(arr, ++left, i++);
            }else if(arr[i] == pivot) {
                i++;
            }else {
                // arr[i] > pivot
                swap(arr, --right, i);
            }
        }

        // 3.区域情况:
        // [l, left]     [letf + 1, right - 1]    [right, r]
        //   < pivot         = pivot                > pivot
        //    a               b                      c
        int a = left - l + 1;
        int b = right - left - 1;
        // int c = r - right + 1;
        if(a >= k) {
            quickSelect(arr, l, left, k);
        }else if(a + b >= k) {
            return;
        }else {
            quickSelect(arr, right, r, k - a - b);
        }
    }

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

//    public int[] smallestK1(int[] arr, int k) {
//        int[] nums = new int[0];
//        if(k == 0) {
//            return nums;
//        }
//        quickSelect(arr, 0, arr.length - 1, k);
//        int index = 0;
//        for(int i = 0; i < arr.length; i++) {
//            if(arr[i] == pivot) {
//                index = i;
//            }
//        }
//
//        nums = Arrays.copyOf(arr, arr.length - 1 - index - 1);
//        return nums;
//    }
//
//    public int quickSelect1(int[] arr, int l, int r, int k) {
//        if(l >= r) {
//            return l;
//        }
//        // 1.随机选择基准元素
//        // int pivotIndex = ;
//        int pivot = arr[new Random().nextInt(r - l + 1) + l];
//
//        // 2.定义三个指针划分区域
//        int left = l - 1, i = l, right = r + 1;
//        while(i < right) {
//            if(arr[i] < pivot) {
//                swap(arr, ++left, i++);
//            }else if(arr[i] == pivot) {
//                i++;
//            }else {
//                // arr[i] > pivot
//                swap(arr, --right, i);
//            }
//        }
//
//        // 3.区域情况:
//        // [l, left]     [letf + 1, right - 1]    [right, r]
//        //   < pivot         = pivot                > pivot
//        //    a               b                      c
//        int a = left - l + 1;
//        int b = right - left - 1;
//        // int c = r - right + 1;
//        if(a >= k) {
//            return quickSelect(arr, l, left, k);
//        }else if(a + b >= k) {
//            return pivot;
//        }else {
//            return quickSelect(arr, right, r, k - a - b);
//        }
//    }
}
